package 二叉树

/*
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked

105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
*/

var (
	m map[int]int
)

func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}

	m = make(map[int]int)
	for i, v := range inorder {
		m[v] = i
	}

	root := build(preorder, inorder, 0, 0, len(inorder)-1)
	return root
}

func build(pre []int, in []int, rPreIndex, l, r int) *TreeNode {
	if l > r {
		return nil
	}

	rVal := pre[rPreIndex]
	rInIndex := m[rVal]
	node := &TreeNode{Val: rVal}

	node.Left = build(pre, in, rPreIndex+1, l, rInIndex-1)
	node.Right = build(pre, in, rPreIndex+(rInIndex-l)+1, rInIndex+1, r)

	return node
}
